package com.dycong.common.leetcode.sort;

import java.util.Arrays;

/**
 * 作用描述:
 *
 * @author dycong
 * @date 2020/1/6 10:47
 */
public class InsertSort {

    public static void main(String[] args) {
        InsertSort bubbleSort = new InsertSort();
        int[] ints = bubbleSort.sort(new int[]{1, 2, 5, 8, 6, 5, 9, 5, 55, 5});
        System.out.println(Arrays.toString(ints));
    }

    /**
     * insert sort
     *
     * @param nums
     * @return
     */
    public int[] sort(int[] nums) {
        if (nums.length < 2) {
            return nums;
        }

        for (int i = 1; i < nums.length; i++) {
            int curIElement = nums[i];
            int j = i;
            for (; j > 0 && nums[j - 1] >= curIElement; j--) {
                nums[j] = nums[j - 1];
            }
            nums[j] = curIElement;
        }
        return nums;
    }
}
